The problem of minimizing a separable convex function under linearly coupledconstraints arises from various application domains such as economic systems,distributed control, and network flow. The main challenge for solving thisproblem is that the size of data is very large, which makes usualgradient-based methods infeasible. Recently, Necoara, Nesterov, and Glineur[Journal of Optimization Theory and Applications, 173 (2017) 227-2254] proposedan efficient randomized coordinate descent method to solve this type ofoptimization problems and presented an appealing convergence analysis. In thispaper, we develop new techniques to analyze the convergence of such algorithms,which are able to greatly improve the results presented there. This refinedresult is achieved by extending Nesterov's second technique developed byNesterov [SIAM J. Optim. 22 (2012) 341-362] to the general optimizationproblems with linearly coupled constraints. A novel technique in our analysisis to establish the basis vectors for the subspace of the linearly constraints.
展开▼
机译：在线性耦合约束下使可分离凸函数最小化的问题源于各种应用领域，例如经济系统，分布式控制和网络流量。解决此问题的主要挑战是数据量很大，这使得基于梯度的常规方法不可行。最近，Necoara，Nesterov和Glineur [优化理论与应用学报，173（2017）227-2254]提出了一种有效的随机坐标下降方法来解决这类优化问题，并提出了一种有吸引力的收敛性分析。在本文中，我们开发了新技术来分析此类算法的收敛性，能够极大地改善此处提出的结果。通过扩展涅斯特罗夫（Nesterov）开发的内斯特罗夫的第二项技术[SIAM J. Optim。 22（2012）341-362]中的一般优化问题具有线性耦合约束。我们分析中的一种新技术是为线性约束的子空间建立基向量。
展开▼
